#include <bits/stdc++.h>
using namespace std;
using ll = long long;
constexpr int N = 100005;
constexpr int M = 200005;
struct edge{int u,v;}e[M];
int n, m, q;
int head[N], to[M << 1], nxt[M << 1], tot = 1;
int dfn[N], low[N], timer;
int stk[N], top;
int del[N], ebcc_cnt;
int dep[N], fa[N], up[N];
void add(int u, int v) {
    nxt[++tot] = head[u];
    head[u] = tot;
    to[tot] = v;
}
void tarjan(int u, int e) {
    dfn[u] = low[u] = ++timer;
    stk[++top] = u;
    for (int i = head[u]; i; i = nxt[i]) {
        if ((i ^ 1) == e) continue;
        int v = to[i];
        if (!dfn[v]) {
            tarjan(v, i);
            low[u] = std::min(low[u], low[v]);
        } else if (dfn[v] < dfn[u]) {
            low[u] = std::min(low[u], dfn[v]);
        }
    }

    if (dfn[u] == low[u]) {
        ++ebcc_cnt;
        do {
            del[stk[top]] = ebcc_cnt;
        } while (stk[top--] != u);
    }
}

void init() {
    tot = 1, ebcc_cnt = 0;
    timer = 0;
    for (int i = 0; i <= n; i++) head[i] = dfn[i] = low[i] = del[i] = 0;
}
void dfs(int u, int f) {
    up[u] = f;
    fa[u] = u;
    dep[u]=dep[f]+1;
    for (int i = head[u]; i; i = nxt[i]) {
        int v = to[i];
        if (v != f) {
            dfs(v, u);
        }
    }
}
int find(int x) { return x == fa[x] ? x : (fa[x] = find(fa[x])); }
bool merge(int x, int y) {
    x = find(x);
    y = find(y);
    if (x == y) return false;
    if(dep[x]<dep[y])fa[y] = x;
    else fa[x]=y;
    return true;
}
void link(int x,int y){
    x=find(del[x]);y=find(del[y]);
    while(x!=y){
        if(dep[x]>=dep[y]){
            merge(x,up[x]);
            x=find(x);
        }else{
            merge(y,up[y]);
            y=find(y);
        }
        ebcc_cnt--;
    }
}
int tc=0;
void fc() {
    init();
    for (int i = 0; i < m; i++) {
        int u, v;
        std::cin >> u >> v;
        e[i].u=u;e[i].v=v;
        add(u, v);
        add(v, u);
    }

    tarjan(1, 0);

    tot = 0;
    for (int i = 1; i <= ebcc_cnt; i++) head[i] = 0;
    for(int i=0;i<m;i++){
        int u=del[e[i].u],v=del[e[i].v];
        if(u!=v)add(u,v),add(v,u);
    }
    dfs(1, 0);

    std::cout << "Case " << ++tc << ":\n";
    std::cin >> q;
    for (int i = 1; i <= q; i++) {
        int u, v;
        std::cin >> u >> v;
        link(u,v);
        std::cout<<ebcc_cnt-1<<"\n";
    }
    std::cout<<"\n";
    std::cin >> n >> m;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    std::cin >> n >> m;
    while (n && m) fc();
    return 0;
}